APIO2020 体验记

比赛

平心而论，这一场的暴力并不比 APIO2019 少很多，所以如果策略不失误的话几十分是肯定有的。但是一直在刚 T1，期间短暂的思考过 T2，T1 不知道是什么恶心数据把我卡了= = 于是就爆 0 了 没有体会到拿分的快感

所以策略是多么重要啊，开题顺序不会永远是 1->2->3 的啊。

下面就放一些订正的题解吧。

A

预处理 + 单调队列，最优性问题 -> 判定性问题

由于保证了 $\sum f(k)^2 \leq 4e5$，所以 $max(f(k))$ 最大就 600 多，虽然很粗糙但这是我们得到的最为有效的信息

只讲预处理。$dp[i, j]$ 表示到位置 $i$、承包商 $j$ 的最大粉刷长度，$dp[i, j] \geq m$ 那 $[i - m + 1, i]$ 就能被粉刷。

$dp[i, j] = dp[i - 1, (j - 1 + m) \% m] + 1(j \in c_i)$，这样时空都是 $O(nm)$ 的，空间可以滚动数组优化，时间可以用 $vector$ 存每个位置合法的 $j$，这样大概是 $O(n * max(f(k)))$，稳得很

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "paint.h"
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 1e5 + 10, M = 5e4 + 10;
int n, m, K, C[N], A[M], B[N], f[2][M], dp[N], q[N], l, r;
bool valid[N];
vector<int> c, a, id[N];
vector<vector<int> > b;

int minimumInstructions(int n, int m, int K, std::vector<int> c, std::vector<int> a, std::vector<std::vector<int> > b) {
    int x = 0;
    rep(i, 0, m - 1) {
        rep(j, 0, a[i] - 1) {
            id[b[i][j]].push_back(i);
        }
    }
    rep(i, 0, n - 1) {
        x ^= 1;
        if (i > 1) {
            for (int k = 0; k < id[c[i - 2]].size(); k++) {
                int j = id[c[i - 2]][k];
                f[x][j] = 0;
            }
        }
        for (int k = 0; k < id[c[i]].size(); k++) {
            int j = id[c[i]][k];
            f[x][j] = f[x ^ 1][(j - 1 + m) % m] + 1;
            if (f[x][j] >= m) valid[i] = 1;
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    q[l = r = 1] = 0;
    rep(i, 1, n) {
        while (l <= r && q[l] < i - m) ++l;
        if (l <= r && valid[i - 1]) dp[i] = dp[q[l]] + 1;
        while (l <= r && dp[q[r]] >= dp[i]) --r;
        q[++r] = i;
    }
    if (dp[n] > 1e9) return -1;
    return dp[n];
}

B

求的是最小非链状瓶颈路，可以在求最小瓶颈路的算法——$kruskal$重构树上略作修改。

具体来说，加边的时候就不要舍弃边了，都加上。考虑$kruskal$重构树的性质，一个点权为 $w$ 的节点子树内的点组成一个边权不超过 $w$ 的连通块。对于每个重构树上的节点，维护一个标记表示它对应的连通块是否是非链状路。非链状路的关系可以传递，即如果儿子的标记 $= 1$ 那么父亲的标记也 $= 1$。每次询问倍增找第一个标记 $= 1$ 的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include "swap.h"
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 3e5 + 10;
int n, m, Q, U[N], V[N], W[N], f[N][21], fa[N], idx, deg[N], dep[N], val[N];
vector<int> u, v, w, g[N];
bool mark[N];
struct edge { int x, y, z; }e[N];

int getfa(int x) {
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

bool cmp(edge a, edge b) { return a.z < b.z; }

void dfs(int x) {
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        dep[y] = dep[x] + 1;
        dfs(y);
    }
}

void Kruskal() {
    rep(i, 1, n) fa[i] = i;
    sort(e + 1, e + m + 1, cmp);
    idx = n;
    rep(i, 1, m) {
        int x = getfa(e[i].x), y = getfa(e[i].y), z = e[i].z;
        ++idx;
        if (x == y) {
            val[idx] = z;
            f[x][0] = idx;
            fa[x] = fa[idx] = idx;
            mark[idx] = 1;
            g[idx].push_back(x);
        } else {
            val[idx] = z;
            f[x][0] = f[y][0] = idx;
            fa[x] = fa[y] = fa[idx] = idx;
            if (mark[x] || mark[y] || (++deg[e[i].x]) > 2 || (++deg[e[i].y]) > 2)  // 子树中存在非链状块
                mark[idx] = 1;
            g[idx].push_back(x), g[idx].push_back(y);
        }
    }
    mark[0] = 1;

    rep(j, 1, 19)
        rep(i, 1, idx)
            f[i][j] = f[f[i][j - 1]][j - 1];
    dep[0] = 0;
    dfs(idx);
}

void init(int nn, int mm,
          std::vector<int> u, std::vector<int> v, std::vector<int> w) {
    n = nn, m = mm;
    for (int i = 0; i < m; i++)
        e[i + 1] = (edge){u[i] + 1, v[i] + 1, w[i]};
    Kruskal();
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 19; i >= 0; --i)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

int getMinimumFuelCapacity(int x, int y) {
    int xy = lca(++x, ++y);
    if (mark[xy]) return val[xy];
    for (int i = 19; i >= 0; i--)
        if (!mark[f[xy][i]]) xy = f[xy][i];
    xy = f[xy][0];
    return xy ? val[xy] : -1;
}

C

咕咕？

upd：补了

度数最大为 $3$ ！！！

考虑知道树的形态了怎么做。「每个点出现一次」暗示了经典模型：有 $sum$ 个物品被划分为若干集合，每次可选两个不同集合的物品匹配并抵消。将子树按最大深度从大到小排，从最深点出发，跳到次深子树，再跳回最深子树，如此反复。显然只要不存在一个子树 $size > n / 2$ 就可以消完。

所以应该选重心作为根。在 $mx 2 < tot$ 时我们优先选深的。在 $mx 2 = tot$ 时我们开始要每条边都经过 $mx$ 了。

如何找重心？以 $1$ 为根 $n$ 次询问每个点的子树大小，子树大小 $\geq n / 2$ 且最小的就是。

再 $n$ 次询问每个点的深度。接下来只要把每个点分到三个子树里去就好了，询问共 $2n$ 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include "fun.h"
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define per(i, x, y) for (int i = x; i >= y; i--)
#define vi vector<int>
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define gc getchar
#define db double
#define bs bitset
#define ll long long
#define lll __int128
#define ui unsigned int
#define ull unsigned long long
#define pii pair<int, int>
#define clr(x) memset(x, 0, sizeof(x))
#define lbit(x) ((x) & (-(x)))
#define heap priority_queue<int>
#define Go(i, x, v) for (int i = 0, x = (i == v.size() ? 0 : v[i]); i < v.size(); i++, x = (i == v.size() ? 0 : v[i]))
using namespace std;
template <class T> void rd(T &x) {
  x = 0; char ch = gc(); int f = 1;
  for (; !isdigit(ch); ch = gc()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + ch - '0';
  x *= f;
}
template <class T> void cmin(T &x, T y) { x = min(x, y); }
template <class T> void cmax(T &x, T y) { x = max(x, y); }
const int mod = 998244353;
template <class T> T add(T x, T y) { return x + y >= mod ? x + y - mod : x + y; }
template <class T> T sub(T x, T y) { return x - y < 0 ? x - y + mod : x - y; }
template <class T> T mul(T x, T y) { return 1ll * x * y % mod; }
template <class T> void Add(T &x, T y) { x = (x + y >= mod ? x + y - mod : x + y); }
template <class T> void Sub(T &x, T y) { x = (x - y < 0 ? x - y + mod : x - y); }
template <class T> void Mul(T &x, T y) { x = 1ll * x * y % mod; }
template <class T> T qpow(T a, T b = mod - 2) { T ret = 1; for (; b; b >>= 1, Mul(a, a)) if (b & 1) Mul(ret, a); return ret; }
/* ============ Header Template ============ */

const int N = 1e5 + 10;
int sz[N], rt, dep[N], son[5], q[5][N];

int aB(int x, int y) {
  return attractionsBehind(x - 1, y - 1);
}
int hR(int x, int y) {
  return hoursRequired(x - 1, y - 1);
}

bool cmp(int x, int y) {
  return dep[x] < dep[y];
}

int mxd(int x, int y) {
  return dep[q[x][q[x][0] + y]];
}

vi createFunTour(int n, int Q) {
  rep(i, 1, n)
    sz[i] = aB(1, i);
  rep(i, 1, n)
    if (sz[i] >= (n + 1) / 2 && (!rt || sz[i] < sz[rt]))
      rt = i;
  rep(i, 1, n) {
    dep[i] = hR(rt, i);
    if (dep[i] == 1)
      son[++son[0]] = i;
  }
  rep(i, 1, n) if (i ^ rt) {
    bool flg = 0;
    rep(j, 1, son[0] - 1) if (dep[i] == 1 + hR(i, son[j])) {
      flg = 1;
      q[j][++q[j][0]] = i;
      break;
    }
    if (!flg) q[son[0]][++q[son[0]][0]] = i;
  }
  rep(i, 1, son[0]) {
    sort(q[i] + 1, q[i] + q[i][0] + 1, cmp);
  }
  vi ans; ans.clear();
  int pre = 0, p = 0;
  per(i, n - 1, 1) {
    int cur = 0;
    if (p && pre != p)
      cur = p;
    else {
      rep(j, 1, son[0]) if (j ^ pre) {
        if (!p) {
          if ((q[j][0] * 2) > i || (q[j][0] * 2 == i && son[0] == 3 && (!pre || mxd(pre, 1) > mxd(6 - j - pre, 0)))) {  // 可以归并了。
            cur = p = j;  // j 占了剩下空位的 1/2 或 1/2 + 1，接下来每条边都有一端在 j 了
            break;
          }
        }
        if (q[j][0] && (!cur || mxd(j, 0) > mxd(cur, 0)))
          cur = j;
      }
    }
    ans.pb(q[cur][q[cur][0]] - 1), --q[cur][0];
    pre = cur;
  }
  ans.pb(rt - 1);
  return ans;
}